560. 和为 K 的子数组

func subarraySum(nums []int, k int) int {
    cntMap := make(map[int]int, len(nums))
    cntMap[0] = 1

    currentSum := 0
    ans := 0

    for _, num := range nums {
        currentSum+=num

        if val, ok := cntMap[currentSum-k]; ok {
            ans+=val
        }

        cntMap[currentSum]++
    }

    return ans
}

刚开始一直看不懂 currentSum-k 什么意思，后来问了下chatgpt。看下原话：

Note

这段代码的目的是检查当前的前缀和减去目标值 k 是否存在于哈希表 sumCount 中，从而帮助我们找到和为 k 的子数组。我们来详细解析一下：

前缀和的概念：
- 前缀和是指数组中从第一个元素到当前元素的和。例如，对于数组 [1, 2, 3]，其前缀和为：
  - 累计到第一个元素：1
  - 累计到第二个元素：1 + 2 = 3
  - 累计到第三个元素：1 + 2 + 3 = 6
- 在代码中，currentSum 表示当前遍历到某个元素时的前缀和。
为什么要检查 currentSum - k：
- 如果当前前缀和是 currentSum，我们希望找到一个子数组，使得这个子数组的和为 k。
- 设这个子数组的起始位置为 j，那么可以得出：
  $sum (j, i) = currentSum - sum (0, j - 1) = k$
  其中 i 是当前元素的索引。
- 通过变形可以得到：
$sum (0, j - 1) = currentSum - k$
- 这意味着，如果我们能找到某个位置的前缀和等于 currentSum - k，那么从 j 到 i 的子数组的和就是 k。
哈希表的作用：
- 哈希表 sumCount 记录了每个前缀和出现的次数。
- 当我们检查 currentSum - k 是否存在于哈希表中时，如果存在，说明从某个之前的位置到当前的位置形成的子数组的和正好是 k。
- val 是 sumCount[currentSum-k] 的值，表示前缀和为 currentSum - k 的次数，即表示有多少个以该前缀和为起点的子数组的和为 k。
计数更新：
- 如果找到了 val，就说明当前前缀和之前有 val 个起点可以形成和为 k 的子数组，因此我们把 count 增加 val。

总之，这段代码的核心思想是利用前缀和的特性，通过检查哈希表来高效地找到和为 k 的子数组。如果有任何具体的疑问，欢迎继续提问！

关键点是这里：

如果当前前缀和是 currentSum，我们希望找到一个子数组，使得这个子数组的和为 k。
设这个子数组的起始位置为 j

遍历到i时，求以i结尾的子数组的和有哪些是k

这个解释相当清晰，写代码也就几分钟就写完了

前缀和如何求可以看： leetcode-303. 区域和检索 - 数组不可变

本站总访问量次本站访客数人次本文总阅读量次